package com.wyw.leetcode.learning.simple;

import com.wyw.leetcode.simple.parent.Node;

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

/**
 * leetcode topic 589
 *  N叉树的前序遍历
 *
 * @Author Mr Wu    yewen.wu.china@gmail.com
 * <p>
 * Update History:
 * Author        Time            Content
 */
public class Topic589 {

    static List<Integer> result = new ArrayList<>();
    public static void main(String[] args) {
        List<Node> childList2 = new ArrayList();
        Node childA1B0 = new Node(5, new ArrayList<>());
        Node childA1B1 = new Node(6, new ArrayList<>());
        childList2.add(childA1B0);
        childList2.add(childA1B1);

        List<Node> childList1 = new ArrayList();
        Node childA0 = new Node(3, childList2);
        Node childA1 = new Node(2, new ArrayList<>());
        Node childA2 = new Node(4, new ArrayList<>());
        childList1.add(childA0);
        childList1.add(childA1);
        childList1.add(childA2);

        Node root = new Node(1,childList1);
        List<Integer> preorder = preorder(root);
        System.out.println("end");
    }

    /**
     * 递归
     */
    public static List<Integer> preorder(Node root) {
        if(root == null) {
            return result;
        }
        result.add(root.val);
//        if(root.children == null) {
//            return result;
//        }
        for(Node child: root.children) {// 增强for循环遇见null的情况会报错，但是空的集合就会跳过
            preorder(child);
        }
        return result;
    }

    /**
     * 迭代
     */
    public static List<Integer> preorder1(Node root) {
        List<Integer> result = new ArrayList<>();
        Stack<Node> stack = new Stack<>();

        if(root == null) {
            return result;
        }

        stack.push(root);

        while(!stack.isEmpty()) {
            Node pop = stack.pop();
            result.add(pop.val);
            for(int i = pop.children.size()-1; i>=0; i--) {
                stack.add(pop.children.get(i));
            }
        }
        return result;
    }



}
